/**
 * \file graphColoring.c
 * \brief Implementação de funções para coloração de grafos
 */

# include "graphColoring.h"

static int recursionCounter;
static int maxFoundedClique;

static void swapValue (int *array, int a, int b);
static void orderArrayByWeight (int *array, int *weight,int start,int end);
static int calcClique (Graph *g, int *validNodes, int *result);
static int maxClique (Graph *g, int *validNodes, int lowerBound, int upperBound, int *result);

static void swapValue(int *array, int a, int b) {
	int tmp;
	tmp = array[a];
	array[a] = array[b];
	array[b] = tmp;
}
static void orderArrayByWeight (int *array, int *weight, int start, int end) {
	int i,done = 0;
	while (!done) {
		done = 1;
		for (i=start;i<end-1;i++) {
			if (weight[array[i]] < weight[array[i+1]]) {
				swapValue(array,i,i+1);
				done = 0;
			}
		}
	}
}

static int calcClique (Graph *g, int *validNodes, int *clique) {
	// pressupõe-se que o result venha com tamanho necessário e inicializado
	int *order; // array para preservar temporariamente a ordem dos vertices
	int *weight; // array para preservar o peso de cada vertice
	int i,j,nValid;
	order = (int *) malloc(g->nodes*sizeof(int));
	weight = (int *) malloc(g->nodes*sizeof(int));
	for (i=0;i<g->nodes;i++) order[i] = weight[i] = clique[i] = 0;
	nValid = 0;
	for (i=0;i<g->nodes;i++)
		if (validNodes[i]) 
			order[nValid++]= i;
	// array order está agora com os vertices válidos
	for (i=0;i<g->nodes;i++) {
		if (!validNodes[i]) continue;
		for (j=0;j<g->nodes;j++) {
			if (!validNodes[j]) continue;
			if (adjacent(g,i,j)) weight[i]++;
		}
	}
	// array weight[i] tem o número de nodos válidos adjacentes ao nodo i
	orderArrayByWeight(order,weight,0,nValid);
	//free(weight);
	// o array order está agora com uma sequencia de indices ordenada por peso (neste caso numero de vertices adjacentes
	clique[order[0]] = ISCLIQUE; // O nodo com mais indices faz parte do clique
	for (i=1;i<nValid;i++) {
		for (j=0;j<i;j++)
			if (clique[order[j]] == ISCLIQUE &&
				!adjacent(g,order[i],order[j]))
					break;
		if (j == i) clique[order[i]] = ISCLIQUE;
		else clique[order[i]] = ISNOTCLIQUE;
	}
	// O array result tem os nodos que fazem parte do clique.
	for (i=0,j=0;i<nValid;i++)
		if (clique[order[i]] == ISCLIQUE) j++;

	free(order);

	return j;
}

static int maxClique (Graph *g, int *validNodes, int lowerBound, int target, int *clique) {
	// result tem de estar inicializado e tem de ter tamanho necessário.
	int novo,actual,totalLeft = 0;
	int i,j,place,start,end;
	int *order,*value, *newValidNodes, *newClique;
	order = value = NULL;
	// Problema de optimização.. (não quero ter que desligar o pc se o prof se lembrar de colocar aqui algo impossivel).
	recursionCounter++;
	if (recursionCounter > MAX_RECURSION) return MAX_CLIQUE_NOT_FOUND;
	for (i=0;i<g->nodes;i++) {
		clique[i] = ISNOTCLIQUE;
		if (validNodes[i]) totalLeft++;
	}
	if (totalLeft < lowerBound) return MAX_CLIQUE_ALLREADY_FOUNDED;
	actual = calcClique(g,validNodes,clique);
	if (actual >= target) return actual; // Este clique serve o objectivo.
	if (actual > maxFoundedClique) maxFoundedClique = actual; // Actualiza o melhor clique encontrado
	order = (int *) malloc(g->nodes*sizeof(int));
        value = (int *) malloc(g->nodes*sizeof(int));
	for (i=0;i<g->nodes;i++)
		order[i] = value[i] = 0;
	place = 0;
	for (i=0;i<g->nodes;i++) {
		if (clique[i]) {
			order[place++] = i;
			totalLeft--;
		}
	}
	start = place;
	for (i=0;i<g->nodes;i++)
		if (!clique[i]&&validNodes[i])
			order[place++] = i;
	end = place;
	for (i=start;i<end;i++) {
		value[order[i]] = 0;
		for (j=0;j<g->nodes;j++)
			if (validNodes[j] && adjacent(g,order[i],j))
				value[order[i]]++;
	}
	orderArrayByWeight(order,value,start,end);
	free(value);
	for (i=start;i<end;i++) {
		if (actual + totalLeft < lowerBound) {
			free(order);
			return MAX_CLIQUE_ALLREADY_FOUNDED;
		}
		totalLeft--;
		if (clique[order[i]]) continue; // Salta este ciclo!
		newValidNodes = (int *) malloc(g->nodes*sizeof(int));
    		newClique = (int *) malloc(g->nodes*sizeof(int)); // Alocar memória limpa para a recursividade
		for (j=0;j<g->nodes;j++) newValidNodes[j] = newClique[j] = 0;
		for (j=0;j<i;j++) {
			if (validNodes[order[j]] && adjacent(g,order[i],order[j])) {
				newValidNodes[order[j]] = 1;
			}
			else newValidNodes[order[j]] = 0;
		}
		novo = maxClique(g,newValidNodes,actual-1,target-1,newClique);
		if (novo + 1 > actual) {
			actual = novo+1;
			for (j=0;j<g->nodes;j++) clique[j] = newClique[j];
			clique[order[i]] = ISCLIQUE;
			if (actual > maxFoundedClique) maxFoundedClique = actual;
		}
		free(newValidNodes); free(newClique);
		if (actual >= target) break; // objectivo atingido!
	}
	free(order); // Aqui a memória pode ser critica!
	return actual;
}
int colorSubGraph (Graph *g) {
	int clique[g->nodes];
	int colors[g->nodes];
	int sum[g->nodes];
	int i,max=0,cor,j;
	int validNodes[g->nodes];
	for (i=0;i<g->nodes;i++) {
		validNodes[i] = 1;
		clique[i] = ISNOTCLIQUE;
		sum[i] = 0;
	}
	max = maxClique(g,validNodes,0,g->nodes+1,clique);
	cor = 1;
	for (i=0;i<g->nodes;i++) {
		if (clique[i]) {
			sum[cor]++;
			g->color[i] = cor++;
		}
	}
	for (i=0;i<g->nodes;i++) {
		if (!g->color[i]) {
			for (j=1;j<cor;j++) colors[j] = 0;
			for (j=0;j<g->nodes;j++) {
				if (g->color[j]) {
					if (adjacent(g,i,j)) colors[g->color[j]] = -1;
					else if (!colors[g->color[j]]) colors[g->color[j]] = 1;
				}
			}
			for (j=1;j<cor;j++) if (colors[j]>0) if(sum[j]+1<=g->maxColors||!g->maxColors) { g->color[i] = j; sum[j]++; }
			if (!g->color[i]) { g->color[i] = cor; sum[cor]++; cor++;  }
		}
	}
	return cor;
}

int colorGraph (Graph *g) {
	LinkedList *aux,*lst = getConnectedSubGraphs(g);
	aux = lst; Graph *tmp;
	int max[g->nodes];
	int i,k = 0,m=0;
	while (aux) {
		tmp = getData(aux);
		max[k] = colorSubGraph(tmp);
		if (max[k] > m) m = max[k];
		aux = aux->next; k++;
	}
	int j,c,cor = 1;
	int count[g->nodes];
	int coloredNodes = 0;
	for (i=0;i<g->nodes;i++) count[i] = 0;
	while (coloredNodes < g->nodes) {
		aux = lst; k = 0;
		while ((!g->maxColors||count[cor]<g->maxColors)&&aux) {
			tmp = getData(aux);
			for (j=1;j<max[k];j++) {
				c = 0;
				for (i=0;i<tmp->nodes;i++) {
					if (tmp->color[i] == j) c++;
				}
				if (!c) { continue; }
				if (!g->maxColors || (c + count[cor]) <= g->maxColors) {
					count[cor] += c;
					for (i=0;i<tmp->nodes;i++) {
						if (tmp->color[i] == j) {
							tmp->color[i] = -1;
							g->color[tmp->label[i]] = cor;
							coloredNodes++;
						}
					}
					break; // tenta proximo nivel
				}
			}
			aux = aux->next; k++;
		}
		cor++;
	}
	aux = lst;
	while (aux) {
		freeGraph(getData(aux));
		aux = aux->next;
	}
	freeLinkedList(lst);
	return (cor-1);
}
